/* Deterministic Algorithms
*
*
*/

#include "sudoku.h"

struct arg_t {
	Grid g;
	int y;
	int pc;
	bool prog;
};

void* deterministic(void *loop_data); 


bool determine(Grid gIn,Grid g){

	bool progress = TRUE;
	int x, y, s, num, num_procs;
	cell tuple;
	memcpy(g, gIn, sizeof(cell) * 81);
	num_procs = 4;

	pthread_t p_threads[num_procs];
	struct arg_t in[num_procs];

	while (progress){
		progress = FALSE;
                s = 0;

		for (y = 0; y<num_procs; y++){
		        in[y].pc = num_procs;
			in[y].y = y;
			in[y].g = g;
			in[y].prog = progress;
		        pthread_create(&p_threads[y], NULL, deterministic,(void*) &in[y]);
		}


		for (y = 0; y<num_procs; y++){
		        pthread_join(p_threads[y], NULL);
		}
                
                


        }


	return isGridSolved (g);
}

void* deterministic(void *loop_data){
	
	struct arg_t *this_data;

	this_data = (struct arg_t *) loop_data;

	int y = this_data->y;
	int pc = this_data->pc;
	Grid g = this_data->g;
	bool progress = this_data->prog;
	cell tuple;
	int x, s, num;
	s = 0;
		for (; y < GRID_SIZE; y += pc){
                        for (x = 0; x < GRID_SIZE; x++){
				num = bitCount(gridIndex(g,x,y));
                                if(num>1){
                                        printf("Cell=%d:%d\n",x,y);
                                        s = onlyInColumn(g,x,y);
                                        if (s > 0){
                                                //printf("Setting Cell (%d,%d) to %d\n",x,y,s);
                                                setCell(s, &gridIndex(g,x,y));
                                                progress |= unmarkCells(g, x, y);
                                        }
                                        s = onlyInRow(g,x,y);
                                        if (s > 0){
                                                setCell(s, &gridIndex(g,x,y));
                                                //printf("Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress |= unmarkCells(g, x, y);
                                        }
                                        s = onlyInSquare(g,x,y);
                                        if(s > 0){
                                                setCell(s, &gridIndex(g,x,y));
						//printf("Setting Cell (%d,%d) to %d\n",x,y,s);
                                                progress |= unmarkCells(g, x, y);
                                        }
					tuple = rowTuple(g, x, y);
					s = bitCount(tuple);
                                        if(s > 0){
						//printf("Cell=%d:%d\n",x,y);
						//printf(" Row Tuple\n");
                                                progress |= unmarkCellsTuple(g, x, y, tuple, 1);
                                        }
					tuple = columnTuple(g, x, y);
					s = bitCount(tuple);
                                        if(s > 0){
						//printf("Cell=%d:%d\n",x,y);
						//printf(" Column Tuple\n");
                                                progress |= unmarkCellsTuple(g, x, y, tuple, 2);
                                        }
					tuple = squareRowTuple(g, x, y);
					s = bitCount(tuple);
                                        if(s > 0){
						//printf("Cell=%d:%d\n",x,y);
						//printf(" Square Row Tuple\n");
                                                progress |= unmarkCellsTuple(g, x, y, tuple, 3);
                                        }
					tuple = squareColumnTuple(g, x, y);
					s = bitCount(tuple);
                                        if(s > 0){
						//printf("Cell=%d:%d\n",x,y);
						//printf(" Square Column Tuple\n");
                                                progress |= unmarkCellsTuple(g, x, y, tuple, 4);
                                        }				
                                }
                        }
		}
}

int onlyInColumn(Grid g, int x, int y){
	
	cell mask = 0x1;
	cell test;
	int i, j, sum;
	//printf("Only Column Test\n");
	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		//printf("cell:");
		//prtCell(mask,0);
		//printf("\ntest:");
		//prtCell(test,0);
		//printf("\n");
		if(bitCount(test) == 1){
			//printf("Bit test passed\n");
			for (j = 0; j < GRID_SIZE; j++){
				if(j != y){
					test = mask & gridIndex(g,x,j);
					//printf("Column Test %d against %d, Result:",j,y);
					//prtCell(test,0);
					//printf("\n");
					sum = sum + bitCount(test);
				}
			}
			if(sum == 0){
				//printf("Column Check, Found Value\n");
				return i;
			}
		}
		sum = 0;
		mask = 0x1;
	}

	//printf("Column Check, Nothing Found\n");
	return 0;

}

int onlyInRow(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	int i, j, sum;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (j = 0; j < GRID_SIZE; j++){
				if(j != x){
					test = mask & gridIndex(g,j,y);
					sum = sum + bitCount(test);
				}
			}
			if(sum == 0){
				//printf("Row Check, Found Value\n");
				return i;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Row Check, Nothing Found\n");	
	return 0;

}

int onlyInSquare(Grid g, int x, int y){
	
	cell mask = 0x1;
	cell test;
	int sx, sy, sum, i, xi, yi;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (&gridIndex(g, x, y) != &subGridIndex(g, sx, sy, xi, yi)){ // Diff Cells
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				return i;
			}
		}
	sum = 0;
	mask = 0x1;
	}

	//printf("Square Check, Nothing Found\n");
	return 0;
}

cell rowTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell result = 0x0;
	cell test;
	int m, i, j, sum;

	for(m = 0; m < GRID_SIZE; m += SUB_GRID_SIZE){	//Find Subgrid
		if(m <= x && x < (m + SUB_GRID_SIZE)){

			for(i = 1; i <= GRID_SIZE; i++){
				mask = mask << (i-1);
				test = mask & gridIndex(g,x,y);
				if(bitCount(test) == 1){
					for (j = 0; j < GRID_SIZE; j++){
						if(j < m || j >= m + SUB_GRID_SIZE){
							test = mask & gridIndex(g,j,y);
							sum = sum + bitCount(test);
						}
					}
					if(sum == 0){
						//printf("Row Tuple Check, Found Value\n");
						result |= mask;
					}
				}
			sum = 0;
			mask = 0x1;
			}

		}
	}
	//printf("Row Tuple Check, Nothing Found\n");
	return result;
}

cell columnTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int m, i, j, sum;
	//printf("Only Column Test\n");

	for(m = 0; m < GRID_SIZE; m += SUB_GRID_SIZE){	//Find Subgrid
		if(m <= y && y < (m + SUB_GRID_SIZE)){

			for(i = 1; i <= GRID_SIZE; i++){
				mask = mask << (i-1);
				test = mask & gridIndex(g,x,y);
				//printf("cell:");
				//prtCell(mask,0);
				//printf("\ntest:");
				//prtCell(test,0);
				//printf("\n");
				if(bitCount(test) == 1){
					//printf("Bit test passed\n");
					for (j = 0; j < GRID_SIZE; j++){
						if(j < m || j >= (m + SUB_GRID_SIZE)){
							test = mask & gridIndex(g,x,j);
							//printf("Column Test %d against %d, Result:",j,y);
							//prtCell(test,0);
							//printf("\n");
							sum = sum + bitCount(test);
						}
					}
					if(sum == 0){
						//printf("Column Check, Found Value\n");
						result |= mask;
					}
				}
				sum = 0;
				mask = 0x1;
			}
		}
	}


	//printf("Column Tuple Check, Nothing Found\n");
	return result;
}

cell squareColumnTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int sx, sy, sum, i, xi, yi, m, n;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	
	n = x+1;
	m = n%SUB_GRID_SIZE;	//Find Subgrid Column x value
	m++;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (xi != (SUB_GRID_SIZE-m)){ // Avoid Test Cell Row
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				result |= mask;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Square Check, Nothing Found\n");
	return result;
}

cell squareRowTuple(Grid g, int x, int y){

	cell mask = 0x1;
	cell test;
	cell result = 0x0;
	int sx, sy, sum, i, xi, yi, m, n;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	n = y+1;
	m = n%SUB_GRID_SIZE;	//Find Subgrid Row y value
	m++;

	for(i = 1; i <= GRID_SIZE; i++){
		mask = mask << (i-1);
		test = mask & gridIndex(g,x,y);
		if(bitCount(test) == 1){
			for (yi = 0; yi < SUB_GRID_SIZE; yi++){
				for (xi = 0; xi < SUB_GRID_SIZE; xi++){
					if (yi != (SUB_GRID_SIZE-m)){ // Diff Cells
						test = mask & subGridIndex(g, sx, sy, xi, yi);
						sum = sum + bitCount(test);
					}
				}
			}
			/*if(x == 5 && y == 6){
				prtCell(gridIndex(g, x, y), 2);
				printf(" Cell (6,7) Testing %d, Result:%d\n", i, sum);
			}*/
			if(sum == 0){
				//printf("Square Check, Found Value\n");
				result |= mask;
			}
		}
	sum = 0;
	mask = 0x1;
	}
	
	//printf("Square Check, Nothing Found\n");
	return result;
}

